package com.su.ou.yang;

import java.util.Arrays;

public class Test9 {
    public static void main(String[] args) {
        int[][] arr={{1,2},{1,3},{2,3},{2,4}, {3,4}, {3,5}};
        System.out.println(eraseOverlapIntervals(arr));
//         System.out.println(i);
    }
    public static int solve(int[][] num){
        if(num==null||num.length==0){
            return 0;
        }
        Arrays.sort(num,(int[] a,int[] b)->{
            if(a[0]==b[0]){
                return a[1]-b[1];
            }else{
                return a[0]-b[0];
            }
        });
        int count=0;
        for(int i=1;i< num.length;i++){
            for (int j = 0; j <i ; j++) {
                if(num[i][0]>=num[j][0]&&num[i][0]<num[j][1]&&num[i][1]>=num[j][1]){
                    count++;
                }
            }
        }
        return count;
    }
    public  static int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0)
             return 0;
         //先排序
         Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
         //记录区间尾部的位置
         int end = intervals[0][1];
         //需要移除的数量
         int count = 0;
           for (int i = 1; i < intervals.length; i++) {
              if (intervals[i][0] < end) {
                 //如果重叠了，必须要移除一个，所以count要加1，
                 //然后更新尾部的位置，我们取尾部比较小的
                 end = Math.min(end, intervals[i][1]);
                 count++;
                 } else {
                 //如果没有重叠，就不需要移除，只需要更新尾部的位置即可
                 end = intervals[i][1];
                 }
            }
        return count;
         }
}
